package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

class NumberOfSubArraysWithOddSum {
    // 2022-08-25 13:02:01
    public static void main(String[] args) {
        Solution solution = new NumberOfSubArraysWithOddSum().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int numOfSubarrays(int[] arr) {
            int m = 1000000007;
            // 前缀和 + 数学
            int[] sum = new int[arr.length + 1];
            for (int i = 1; i < sum.length; i++) {
                sum[i] = sum[i - 1] + arr[i - 1];
            }

            // 只有奇数和偶数相减才可能为奇数  [0,1,
            int j = 0, o = 0;
            int ans = 0;
            for (int i = 0; i < sum.length; i++) {
                if (sum[i] % 2 == 0) {
                    ans = (ans + j) % m;
                    o++;
                } else {
                    ans = (ans + o) % m;
                    j++;
                }
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}